import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 面试题58-1：翻转单词顺序
 */
public class Offer_58_I {
    /**
     * 方法四：正向遍历，就硬手写
     * <p>
     * <ol>
     * <li>去除字符串开头、末尾的空格，单词之间的空格只保留一个；</li>
     * <li>将整个字符串翻转；</li>
     * <li>将每个单词翻转。</li>
     * </ol>
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public String reverseWords(String s) {
        // 按题意去除空格
        StringBuilder builder = trimSpaces(s);
        // 翻转整个字符串
        reverse(builder, 0, builder.length() - 1);
        // 翻转每个单词
        reverseEachWord(builder);
        return builder.toString();
    }

    /**
     * 去除字符串首尾空格，及单词间多余的空格（只保留一个）
     */
    private StringBuilder trimSpaces(String s) {
        int left = 0, right = s.length() - 1;
        // 去除字符串开头空格
        while (left <= right && s.charAt(left) == ' ') {
            left++;
        }
        // 去除字符串末尾空格
        while (left <= right && s.charAt(right) == ' ') {
            right--;
        }
        // 单词之间空格只保留一个
        StringBuilder builder = new StringBuilder();
        while (left <= right) {
            char ch = s.charAt(left);
            if (ch != ' ') {
                // 如果当前字符不是空格，直接拼接
                builder.append(ch);
            } else if (builder.charAt(builder.length() - 1) != ' ') {
                // 如果当前字符是空格，但它前一个字符不是空格，也将其拼接
                builder.append(ch);
            }
            left++;
        }
        return builder;
    }

    /**
     * 将 StringBuilder 指定区间内的字符翻转
     * 
     * @param builder 要翻转的 StringBuilder
     * @param start   区间开始索引
     * @param end     区间结束索引（包含）
     */
    private void reverse(StringBuilder builder, int start, int end) {
        while (start < end) {
            char temp = builder.charAt(start);
            builder.setCharAt(start, builder.charAt(end));
            builder.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    /**
     * 将 StringBuilder 中每个单词进行翻转
     */
    private void reverseEachWord(StringBuilder builder) {
        int length = builder.length();
        // 单词的开始位置和结束位置
        int start = 0, end = 0;
        while (start < length) {
            // 找到单词结束处
            while (end < length && builder.charAt(end) != ' ') {
                end++;
            }
            // 翻转单词
            reverse(builder, start, end - 1);
            // 下一个单词开始的位置
            start = end + 1;
            // 当前 end 所在位置是空格，将其移到下个单词开始处，不然 end 将不变导致死循环
            end++;
        }
    }

    ////////////////////////////////////////////////////////

    /**
     * 方法三：栈
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public String reverseWords3(String s) {
        int left = 0, right = s.length() - 1;
        // 去掉开头空格
        while (left <= right && s.charAt(left) == ' ') {
            left++;
        }
        // 去掉末尾空格
        while (left <= right && s.charAt(right) == ' ') {
            right--;
        }

        Deque<String> stack = new LinkedList<>();
        StringBuilder word = new StringBuilder();
        while (left <= right) {
            char ch = s.charAt(left);
            if (word.length() > 0 && ch == ' ') {
                // 如果当前单词长度 > 0，并且当前字符是空格，说明一个单词已遍历完
                stack.push(word.toString());
                // 遍历完一个单词后，将 word 的长度重置为 0，或者再 new 一个也行
                word.setLength(0);
            } else if (ch != ' ') {
                // 如果当前单词长度为 0，或者当前字符不是空格，则拼接单词
                word.append(ch);
            }
            // 向后遍历
            left++;
        }
        // 循环结束后，还有一个单词没有入栈，将其入栈
        stack.push(word.toString());

        StringBuilder ans = new StringBuilder();
        // 依次出栈，拼接新的字符串
        while (!stack.isEmpty()) {
            ans.append(stack.pop()).append(" ");
        }
        // 末尾会多出一个空格，将其去掉
        return ans.toString().trim();
    }

    ////////////////////////////////////////////////////////

    /**
     * 方法二：双指针倒序遍历
     * <p>
     * <ol>
     * <li>倒序遍历字符串 s，记录单词左右索引边界 i, j；</li>
     * <li>每确定一个单词的边界，则将其拼接；</li>
     * <li>最终，将单词列表拼接为字符串，并返回即可。</li>
     * </ol>
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public String reverseWords2(String s) {
        // 去除首尾空格
        s = s.trim();
        int i = s.length() - 1, j = i;
        StringBuilder builder = new StringBuilder();
        // 倒序遍历
        while (i >= 0) {
            // 定位首个空格
            while (i >= 0 && s.charAt(i) != ' ') {
                i--;
            }
            // 拼接单词
            builder.append(s, i + 1, j + 1).append(' ');
            // 跳过单词之间的空格
            while (i >= 0 && s.charAt(i) == ' ') {
                i--;
            }
            // j 指向下个单词的尾字符
            j = i;
        }
        // 拼接字符串最后会多出一个' '，需要去掉
        return builder.toString().trim();
    }

    ////////////////////////////////////////////////////////

    /**
     * 方法一：调用 API（面试慎用）
     */
    public String reverseWords1(String s) {
        // 去除字符串首尾空白
        s = s.trim();
        // 按正则表达式拆分字符串
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        // 反转
        Collections.reverse(wordList);
        // 得到新的字符串
        return String.join(" ", wordList);
    }

    public static void main(String[] args) {
        Offer_58_I solution = new Offer_58_I();
        // 测试 1
        String str1 = "the sky is blue";
        String ans1 = solution.reverseWords(str1);
        System.out.println(ans1);
        // 测试 2
        String str2 = "  hello world!  ";
        String ans2 = solution.reverseWords(str2);
        System.out.println(ans2);
        // 测试 3
        String str3 = "a good   example";
        String ans3 = solution.reverseWords(str3);
        System.out.println(ans3);
    }
}
